講完智慧指標後，回到用頭插法解Leetcode 92

impl Solution {
    pub fn reverse_between(
        head: Option<Box<ListNode>>,
        left: i32,
        right: i32,
    ) -> Option<Box<ListNode>> {
        if left == right || head.is_none() {
            return head;
        }

        let mut dummy = Some(Box::new(ListNode { val: 0, next: head }));
        let mut pre = &mut dummy;
        for _ in 1..left {
            pre = &mut pre.as_mut().unwrap().next;
        }

        // curr = B 段原頭
        let mut curr: *mut ListNode  = pre.as_mut().unwrap().next.as_mut().unwrap().as_mut();
        for _ in 0..(right - left) {
            unsafe {
                // 拿出 curr.next
                let mut node = (*curr).next.take().unwrap();
                // tail 跳過 node
                (*curr).next = node.next.take();
                // node 插到 pre 後面
                node.next = pre.as_mut().unwrap().next.take();
                pre.as_mut().unwrap().next = Some(node);
            }
        }

        dummy.unwrap().next
    }
}

跑完A段後，我們在B段把原本&mut轉型成裸指標*mut

let mut curr: *mut ListNode  = pre.as_mut().unwrap().next.as_mut().unwrap().as_mut();

pre.as_mut()                // Option<&mut Box<ListNode>>
   .unwrap()                // &mut Box<ListNode>
   .next                    // &mut Option<Box<ListNode>>
   .as_mut()                // Option<&mut Box<ListNode>>
   .unwrap()                // &mut Box<ListNode>
   .as_mut()                // Box<ListNode>::as_mut -> &mut ListNode // Box<ListNode>::as_mut -> &mut ListNode

let mut curr: *mut ListNode //&mut T 自動可轉裸指標 *mut T

為何需要裸指標

複習一下借用檢查原則

1. 同時允許多個不可變借用 &T

2. 最多只能有一個可變借用 &mut T

3. 1和2不能同時存在。

我們在B段一開始curr就把prev.next node借走了對這個節點有唯一控制權，但在頭插法要加在A段結尾pre.as_mut().unwrap().next，像是借出了兩個 &mut，編譯器無法證明安全。

//沒轉成raw pointer
let mut curr:&mut ListNode  = pre.as_mut().unwrap().next.as_mut().unwrap().as_mut();

for _ in 0..(right - left) {
    unsafe {
        // 拿出 curr.next
        let mut node = (*curr).next.take().unwrap();
        // tail 跳過 node
        (*curr).next = node.next.take();
        // node 插到 pre 後面
        node.next = pre.as_mut().unwrap().next.take();
        pre.as_mut().unwrap().next = Some(node);
    }
}

Unsafe

編譯器在編譯時無法獲取足夠資訊，預設是會擋下來

我們可以用unsafe請編譯器不要檢查這區塊內的寫的code，由撰寫者由撰寫者自己負責。

在 unsafe 區塊裡除了請編譯器不要檢查這區塊內的寫的code，還可以操作safe情況不能做的事：

• 解引用 raw pointer（*const T, *mut T）

• 呼叫 unsafe fn（如 FFI、某些標準庫內部函式）

• 實作 unsafe trait

• 存取/修改 static mut

• 使用 union 不安全欄位

有了這我們就能使用頭插法修改linked list

這題因為leetcode宣告的結構next Option<Box<ListNode>>所以必須用unsafe來避免編譯器檢查，說到這有沒有想到Rc<T>,RefCell<T>

// Definition for singly-linked list.
 #[derive(PartialEq, Eq, Clone, Debug)]
 pub struct ListNode {
   pub val: i32,
   pub next: Option<Box<ListNode>>
 }
 
 impl ListNode {
   #[inline]
   fn new(val: i32) -> Self {
     ListNode {
       next: None,
       val
     }
   }
 }

用Rc<T>,RefCell<T>修改unsafe

依序反轉linked list順序

use std::cell::RefCell;
use std::rc::Rc;

#[derive(Clone, Debug)]
struct Node {
    val: i32,
    next: Option<Rc<RefCell<Node>>>,
}

impl Node {
    fn new(val: i32) -> Rc<RefCell<Self>> {
        Rc::new(RefCell::new(Node { val, next: None }))
    }
}

fn from_vec(v: &[i32]) -> Option<Rc<RefCell<Node>>> {
    let mut head: Option<Rc<RefCell<Node>>> = None;
    for &x in v.iter().rev() {
        let n = Node::new(x);
        n.borrow_mut().next = head;
        head = Some(n);
    }
    head
}

fn to_vec(mut head: Option<Rc<RefCell<Node>>>) -> Vec<i32> {
    let mut out = Vec::new();
    while let Some(rc) = head {
        out.push(rc.borrow().val);
        head = rc.borrow().next.clone();
    }
    out
}

fn reverse_between_rc(
    head: Option<Rc<RefCell<Node>>>,
    left: i32,
    right: i32,
) -> Option<Rc<RefCell<Node>>> {
    if left == right || head.is_none() {
        return head;
    }

    // dummy node to simplify edge cases
    let dummy = Rc::new(RefCell::new(Node { val: 0, next: head.clone() }));
    let mut prev = Rc::clone(&dummy);

    // Move prev to the node before 'left'
    for _ in 0..(left - 1) {
        let next = prev.borrow().next.clone().unwrap();
        prev = next;
    }

    // Start reversing
    let mut curr = prev.borrow().next.clone();
    let mut prev_sub = None;
    for _ in left..=right {
        if let Some(node) = curr.clone() {
            let next = node.borrow().next.clone();
            node.borrow_mut().next = prev_sub;
            prev_sub = Some(node);
            curr = next;
        }
    }

    // Connect the reversed part back
    let left_node = prev.borrow().next.clone().unwrap();
    left_node.borrow_mut().next = curr;
    prev.borrow_mut().next = prev_sub;

    // Return new head
    dummy.borrow().next.clone()
}

fn main() {
    let v = vec![1, 2, 3, 4, 5];
    let head = from_vec(&v);
    let new_head = reverse_between_rc(head, 2, 4);
    let out = to_vec(new_head);
    println!("{:?}", out); // [1, 4, 3, 2, 5]
}

使用頭插法反轉

use std::cell::RefCell;
use std::rc::Rc;

#[derive(Clone, Debug)]
struct Node {
    val: i32,
    next: Option<Rc<RefCell<Node>>>,
}

impl Node {
    fn new(val: i32) -> Rc<RefCell<Self>> {
        Rc::new(RefCell::new(Node { val, next: None }))
    }
}

fn from_vec(v: &[i32]) -> Option<Rc<RefCell<Node>>> {
    let mut head: Option<Rc<RefCell<Node>>> = None;
    for &x in v.iter().rev() {
        let n = Node::new(x);
        n.borrow_mut().next = head;
        head = Some(n);
    }
    head
}

fn to_vec(mut head: Option<Rc<RefCell<Node>>>) -> Vec<i32> {
    let mut out = Vec::new();
    while let Some(rc) = head {
        out.push(rc.borrow().val);
        head = rc.borrow().next.clone();
    }
    out
}

// 頭插法反轉 left~right 節點
fn reverse_between_rc(
    head: Option<Rc<RefCell<Node>>>,
    left: i32,
    right: i32,
) -> Option<Rc<RefCell<Node>>> {
    if left == right || head.is_none() {
        return head;
    }

    // dummy node to簡化邊界
    let dummy = Rc::new(RefCell::new(Node { val: 0, next: head.clone() }));
    let mut prev = Rc::clone(&dummy);

    // prev移到left-1
    for _ in 0..(left - 1) {
        let next = prev.borrow().next.clone().unwrap();
        prev = next;
    }

    // start是left節點
    let start = prev.borrow().next.clone().unwrap();

    // 進行頭插法
    for _ in left..right {
        // 要移動的節點
        let to_move = start.borrow().next.clone().unwrap();

        // start.next 指向 to_move.next
        start.borrow_mut().next = to_move.borrow().next.clone();

        // to_move 插到 prev 後面
        to_move.borrow_mut().next = prev.borrow().next.clone();
        prev.borrow_mut().next = Some(to_move);
    }

    dummy.borrow().next.clone()
}

fn main() {
    let v = vec![1, 2, 3, 4, 5];
    let head = from_vec(&v);
    let new_head = reverse_between_rc(head, 2, 4);
    let out = to_vec(new_head);
    println!("{:?}", out); // [1, 4, 3, 2, 5]
}

input  = [1, 2, 3, 4, 5]
output = [1, 4, 3, 2, 5]

Day21 總結

1. Rust 裸指標
2. Rust unsafe用法

參考資料

1. https://rust-lang.tw/book-tw/ch19-01-unsafe-rust.html